The invention relates to public key cryptography, and more particularly to the exchange of keys over insecure communications channels.
The problem of distributing keys for cryptographic purposes is well known. Diffie and Hellman introduced the concept of public-key cryptography, allowing for the first time the possibility of secure communication over an insecure channel without the need for some other secure channel through which to first distribute cryptographic keys. Public key cryptography according to Diffie and Hellman provides a practical and secure scheme for establishing shared secret keys between communicating parties through the exchange of publicly observable information. Their method involves exponentiation in a finite field and its security relies on the computational intractability of inverting such exponentiations, that is, of finding discrete logarithms in a finite field.
In its basic form the Diffie-Hellman key-agreement protocol proceeds as follows (with all exponentiations being modular exponentiations with modulus p):
1) An appropriate prime p and a generator g of Z.sub.p *, the multiplicative group of residue classes modulo p, with 2.ltoreq.g.ltoreq.p-2, are selected and published. PA1 2) Each time participants A and B require a shared key:
A chooses a random secret x with 1.ltoreq.x.ltoreq.p-2 and sends g.sup.x modp to B. PA2 B chooses a random secret y with 1.ltoreq.y.ltoreq.p-2 and sends g.sup.y modp to A. PA2 B receives g.sup.x and computes the common shared key as ##EQU1## A receives g.sup.y and computes the common shared key as ##EQU2## A and B's keys are identical because ##EQU3## An eavesdropper who sees g.sup.x modp and g.sup.y modp in transmission cannot feasibly calculate g.sup.xy modp because of the believed computational intractability of discovering x from g.sup.x modp or y from g.sup.y modp.
It is well-known to those practiced in the art that these techniques are applicable to Diffie-Hellman key exchange using other finite groups, in particular the multiplicative group of finite fields of characteristic 2, and elliptic curve groups over finite fields.
For each participant, the above protocol involves the computation of two modular exponentiations. To perform this calculation, public-key agreement techniques typically impose a computational burden comparable to performing several hundred modular multiplications over a field of several hundred bits in length.
The above protocol provides no authentication of keys, and so is vulnerable to a man-in-the-middle attack in which participants A and B end up each exchanging keys with the attacker instead of with each other. One variation of the protocol that provides mutual key authentication and so overcomes this problem is to fix g.sup.x modp and g.sup.y modp as the long-term public keys of A and B respectively, and to distribute these keys using certificates signed by a mutually trusted third party or parties. This fixes the long-term secret shared key for this pair of users as g.sup.xy modp. Prudent security practices well known to those skilled in the art dictate that such a key, being time-invariant in nature, should not be directly used as the session key, but rather that session keys should be freshly derived from the long-term shared secret key in such a way as not to compromise it should the session keys themselves become revealed to an attacker. Although verification of the signatures on certificates adds to the computational load, there are public-key signature schemes for which the verification operation needs only one or two modular multiplications, for example, RSA signatures with a public exponent of 3, or modified-Rabin signatures.
For widespread application of public-key techniques in consumer electronics devices there is a need to reduce the computational burden to that which an inexpensive device such as a single chip microcontroller can perform in a fraction of a second. One such example application is key-agreement for the encrypted transmittal of copyright-protected digital video streams between a consumer electronics playback device, such as a digital video disk (DVD) player, and a digital television, wherein the data is desired to be encrypted in transit between the two devices in order to protect the data from unauthorized copying.
One way to decrease the computational burden on the parties is to reduce the number of operations required to perform modular exponentiation. One way to do this is to pre-compute and store as much of the overall exponentiation computation as possible. Another way that has been suggested to improve computational economy is the use of exponents of restricted form. For example, the U.S. government's Digital Signature Algorithm uses short exponents whose length is just 160 bits despite the fact that modular exponentiation is performed using a modulus whose size may vary from 512 bits to 1024 bits. The standard method of direct attack against a short exponent is a meet-in-the-middle attack. Such attacks have complexity that is approximately exponential in half the length of the exponent, that is, on the order of the square-root of the number of possible values that the exponent can take. A common choice of exponent length is 160 bits for proof against a meet-in-the-middle attack needing about 2.sup.80 operations, which is believed to be comfortably beyond reach with current technology. A prime field offering comparable resistance to the calculation of discrete logarithms needs to be somewhere between 512 and 1024 bits in length.